#ifndef SKIPLIST_H_
#define SKIPLIST_H_

#include<stdlib.h>
#include<list>
#include<iterator>
#include<iostream>
#include<iomanip>

/**
* Expected number of nodes : 2*N
* Expected height (with high probability) : O( log N )
* Insertion O( log N )
* Search    O( log N )
* Deletion  O( log N )
* usees a (-inf) sentinel node on each level
*/
template <class T>
class SkipList 
{
	public:
	
	void insert(T v);

	bool search(T v);

	void clear();

	void erase(T v);

	void print();
	
	int height();
	/**
	*@return total number of nodes
	*/
	int count_nodes();

	SkipList<T>(): root(new Node()){} 
	
	~SkipList<T>(){ remove_all(); }

	private:

	struct Node
	{
		Node* nx,* dw;
		T data;

		Node():nx(NULL), dw(NULL){}
		Node(T data):data(data), nx(NULL), dw(NULL){}
	};
	

	Node* insert(Node* b, T v);
	
	bool search(Node* b, T v);

	void erase(Node* b, T v);
	/**
	*dealocate all the node 
	*/
	void remove_all();
	/**
	*Reference to the first -inf node
	*/
	Node* root;
};
#include "skiplist.cpp"
#endif // SKIPLIST_H_
